這章節介紹Quick Sort，它是目前公認最快的sort方法，其核心概念使用了partition的想法。

Quick sort是在1960年一位Tony Hoare發明的，當時的電腦還是用磁帶組成，不像現在的RAM這麼好用。以下為他當時想到partition的想法：

選定其中一個元素稱為pivot，把剩下的元素依據pivot分兩邊。

而Quick Sort就是不斷進行這個步驟，直到sort完畢：

1. 選定一個元素，稱為pivot
2. 將剩餘的元素分類，小於pivot的一邊，大於pivot的一邊
3. 然後再從兩群中選出各自的pivot，直到sort完畢

以下來討論他的runtime：

在最佳的情形下，會是N log N：

而最差的情形下就會是N^2：

看到這邊我就很疑惑了，因為先前介紹的merge sort不管什麼狀況都可以達到N log N，為什麼還要用這個Quick Sort? 居然還說它是最快的sort? 可以提出一些直觀的看法，因為其實要遇到N^2的可能性趨近於0：

第一個是假設只要我們選定的pivot在前10%左右的位子就好，不奢求會選到正中間，已經很寬容了吧，其效率一樣會是N log N：

再來是我們會發現其實它整個過程根本就是在建立出一棵BST：

但以上的論證都是提供一個直觀的想法，如果真要證明它就是最快的sort方法，只能使用經驗法則(empirical)加上統計來證明了，這邊不討論太多詳細的數學哈哈：

以下總結目前遇到的sort方法比較：

接著我們來繼續討論一些實作Quick Sort的細節。

我們知道若pivot選得好，quick sort會是一個比merge sort更快的方法，但問題就在於該如何避免我們選到很爛的pivot導致我們的quick sort不快呢？

• pivot selection

  • randomness

  以下關於randomness的投影片提到兩種做法，一種是隨機挑選pivot，另一種是先shuffle array後再一樣挑第一個當pivot：

  

  • smart pivot selection

  關於選擇pivot的做法，這邊提供了兩種想法：

  2a. 做一些前處理，比如選三個然後挑中間大小的那個，但要確保前處理是constant time。

  

  2b. 直接先找到median，然後再進行quick sort，但是這樣變成比merge sort慢。

  BFPRT can find exact median by theta(N), linear time

  • Introspection

  先試著做做看，若執行時間超過某個閥值，再切換成merge sort。

  

那發明Quick Sort的Tony Hoare本人是如何實作Quick Sort的呢？

Tony Hoare’s in place partitioning scheme：

1. 一樣會先選定一個pivot，只不過它會有兩個pointer，一個從頭一個從尾。
2. 頭pointer會略過比pivot小的，而當它遇到比pivot大的值時，開始來看尾pointer。
3. 尾pointer相反，會略過比pivot大的，而當它遇到比pivot小的值時，會和頭pointer互換，然後兩個pointer一起都往前一步
4. 然後回到步驟2，直到某一邊的pointer跨過另一個pointer
5. 這時，跨過另一個pointer的當前位置再和pivot互換，就完成了。

動畫投影片：

https://docs.google.com/presentation/d/1DOnWS59PJOa-LaBfttPRseIpwLGefZkn450TMSSUiQY/pub?start=false&loop=false&delayms=3000

目前談到的各種實現總結：

• quick select

我們再談quick sort時，都知道若能找到median，那就太棒了，是個完美的quick sort。神奇的是，其實partitioning的概念也同樣很適合拿來找median！

• is a sort algorithm stable or not?

在談了幾種sort後，有一個議題可以拿來討論看看，那就是stability。甚麼是stability？就是指在sort前跟sort後，各個元素的初始順序有沒有變化，可以看看以下的範例，範例試圖sort一個column有name和section number的表，然後根據section number來sort，可以知道因為section number有重複的，所以就算不符合初始順序，也能是正確的結果，但就是有stable or not的問題：

以下是stable的結果：

以下是not stable的結果：

隨著後進的加入，到現今已經發現了各種各樣的quick sort實作方法，以下投影片提及了一些比較有名的例子：

• optimizing sort according situations, ex: Tim sort, make sort adaptive

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License